// S is a collection for handling substrings of a master string. It allows for
//easy manipulation of the substrings and creation of new substrings.
// A Finder is an object that divides a string into substrings.
// A matcher matches strings and can be used to filter substrings.
// A Replacer replaces strings and can be used to rewrite only substrings.
// Despite the repeated use of the word string, here we mean []byte.
package substr

// The substring intervals in S.Idx are a list of pairs:
//         [(s0,e0), (s1,e1), ..., (sI,eI), ..., (sN,eN)]
//such that
//         0 <= s0 <= e0 <= ... <= sI <= eI <= ... <= sN <= eN <= len(S.Super),
//and for any valid index i, len(S.Subs[i]) == 2.
// These invariants are enforced by all mutating operations, unless otherwise
//specified.
//
// UTF-8 runes are not inherently respected by this library.
//
//It is not recommended to alter the exposed fields except by the provided
//methods unless you no longer need the S object or are writing a custom Finder
//and know what you are doing.
type S struct {
	Super []byte
	Subs  [][]int
}

const default_sz = 16

// Create a new S object from a byte slice. The second parameter is the capacity
//to preallocate for indicies. If sz < 0, uses a sane default value. It is safe
//to pass the n parameter of a Finder directly to New.
func New(s []byte, sz int) *S {
	var is [][]int
	if sz < 0 {
		sz = default_sz
	}
	is = make([][]int, 0, sz)
	return &S{s, is}
}

//Increase the capacity of the indicies vector. Given l := len(s.Subs),
//if cp < l, then l-cp elements will be cloven from the end and afterwards,
//len(s.Subs) is cap(s.Subs).
func (s *S) Resize(cp int) {
	ln := len(s.Subs)
	if cp < ln {
		ln = cp
	}
	new := make([][]int, ln, cp)
	copy(new, s.Subs)
	s.Subs = new
}

//Verify that all the substrings are valid. This is not intended for ordinary
//use--it is only meant as an aid to debugging a finder.
func DebugVerify(s *S) bool {
	return DebugVerifyRaw(s.Subs, len(s.Super))
}

//Verify a raw [][]int representing substrings. Requires an integer representing
//the length of the string to verify the last substring. This is only meant
//for debugging a finder.
func DebugVerifyRaw(is [][]int, ln int) bool {
	if is == nil {
		return true
	}
	a, b := is[0][0], is[0][1]
	if len(is) == 1 {
		return 0 <= a && a <= ln && a <= b && b <= ln
	}
	if !(0 <= a && a <= b && a <= ln) {
		return false
	}
	var next int
	for i, v := range is[0 : len(is)-1] {
		a, b, next = v[0], v[1], is[i+1][0]
		if !(0 <= a && a <= b && b <= next && b <= ln) {
			return false
		}
	}
	last := is[len(is)-1]
	a, b = last[0], last[1]
	return a <= b && b <= ln
}

//Test if two substring indicies are equal. This is only meant as a debugging
//aid.
func DebugEqual(a, b [][]int) bool {
	if len(a) != len(b) {
		return false
	}
	for i, v1 := range a {
		v2 := b[i]
		if len(v1) != 2 || len(v2) != 2 || v1[0] != v2[0] || v1[1] != v2[1] {
			return false
		}
	}
	return true
}
